package leetcode

import kotlin.math.max

/*
*       https://leetcode.com/problems/house-robber/
*
*       You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed,
*       the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and
*       it will automatically contact the police if two adjacent houses were broken into on the same night.
*
*       Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of
*       money you can rob tonight without alerting the police.
*
*
*       Example 1:
*
*       Input: nums = [1,2,3,1]
*       Output: 4
*       Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
                    Total amount you can rob = 1 + 3 = 4.
*       Example 2:

*       Input: nums = [2,7,9,3,1]
*       Output: 12
*       Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
                    Total amount you can rob = 2 + 9 + 1 = 12.
* */
fun main(args: Array<String>) {

    val src = intArrayOf(1, 3, 1)

    println(rob(src))
}


fun rob(nums: IntArray): Int {

    if (nums.size == 1)
        return nums[0]

    if (nums.size == 2)
        return max(nums[0], nums[1])

    val dp = IntArray(nums.size) { 0 }

    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for (i in 2 until nums.size)
        dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2])

    return dp[nums.lastIndex]

}